/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package estructuras;

import hoja7.Estudiante;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Vector;

/**
 *
 * @author asus
 * Implementación de heap utilizando un vector, basada parcialmente en el código indicado en el libro del curso
 */
public class ArrayListPQ<E extends Comparable<E>> extends AbstractHeap<E> implements PriorityQueue<E> {
    
    private Vector<E> data;
    
    public ArrayListPQ() {
        data = new Vector<E>();
    }
    
    public int size() {
       return data.size(); 
    }
    
    public E getFirst() {
        return data.get(0);
    }
    
    public E remove(Comparator c) {
        E minVal = getFirst();
        data.set(0,data.get(data.size()-1));
        data.setSize(data.size()-1);
        if (data.size() > 1) pushDownRoot(0, c);
        return minVal;
    }
 
    public E remove() {
        E minVal = getFirst();
        data.set(0,data.get(data.size()-1));
        data.setSize(data.size()-1);
        if (data.size() > 1) pushDownRoot(0);
        return minVal;
    }
    
    public void add(E o, Comparator c) {
        data.add((E) o);
        percolateUp(data.size()-1, c);
    }
    
    public void add(E o) {
        data.add((E) o);
        percolateUp(data.size()-1);
    }
    
    protected static int parent(int i) {
        return (i-1)/2;
    }
    
    protected static int left(int i) {
        return 2*i+1;
    }
    
    protected static int right(int i) {
        return 2*(i+1);
    }
    
    protected void percolateUp(int leaf, Comparator chomp) {
        int parent = parent(leaf);
        E value = data.get(leaf);
        while (leaf > 0 &&
            (chomp.compare(value, data.get(parent)) < 0)) {
        data.set(leaf,data.get(parent));
        leaf = parent;
        parent = parent(leaf);
        }
        data.set(leaf,value);
    }
    
    protected void percolateUp(int leaf) {
        int parent = parent(leaf);
        E value = data.get(leaf);
        while (leaf > 0 && (value.compareTo(data.get(parent)) < 0)) {
            data.set(leaf,data.get(parent));
            leaf = parent;
            parent = parent(leaf);
        }
        data.set(leaf,value);
    }
    
    protected void pushDownRoot(int root, Comparator chomp) {
        int heapSize = data.size();
        E value = data.get(root);
        while (root < heapSize) {
            int childpos = left(root);
            if (childpos < heapSize) {
                if ((right(root) < heapSize) && (chomp.compare(data.get(childpos+1), data.get(childpos)) < 0)) {
                    childpos++;
                }

            if (chomp.compare(data.get(childpos), value) < 0) {
                data.set(root,data.get(childpos));
                root = childpos; // keep moving down
            } else { 
                data.set(root,value);
                return;
            }
            } else { // at a leaf! insert and halt
                data.set(root,value);
                return;
            }
       }
    }
    
    
    protected void pushDownRoot(int root) {
        int heapSize = data.size();
        E value = data.get(root);
        while (root < heapSize) {
            int childpos = left(root);
            if (childpos < heapSize) {
                if ((right(root) < heapSize) && ((data.get(childpos+1)).compareTo (data.get(childpos)) < 0)) {
                    childpos++;
                }
                if ((data.get(childpos)).compareTo(value) < 0){
                    data.set(root,data.get(childpos));
                    root = childpos; // keep moving down
                } else { // found right location
                    data.set(root,value);
                    return;
                }
            } else { // at a leaf! insert and halt
                data.set(root,value);
                return;
            }
        }
    }
}
